home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 126-150 / disk_142 / diff / diff.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  38KB  |  1,731 lines
  1. /*
  2.  * Last Hacked by Johan Widen, jw@sics.se, 17 Jan 88.
  3.  *   Decreased memory use by cleaning up the data types. "new style" context
  4.  *   diffs. File dates are now displayed under UNIX and Amiga-DOS.
  5.  *   Incorporated documentation cleanup and TURBO-C adaptions by mike2@lcuxa.
  6.  *
  7.  * Previously Hacked by Robert A. Larson, blarson@ecla.usc.edu, Nov 29 86
  8.  *   OSK support.
  9.  *   Real context diffs, with a couple of minor problems:
  10.  *      If the first change is deleting leading lines, and the second
  11.  *    such that the context overlaps the deleted lines, the deleted
  12.  *    lines are output as context.  This is consistant with other
  13.  *    cases of overlapping context, but patch doesn't like it.  It's
  14.  *    not hard to manually fix the diff in this (rare?) case.
  15.  *      At most 9 lines of context is output.
  16.  *
  17.  * Previously Hacked by John Gilmore, hoptoad!gnu, 26Sep86.
  18.  * Compiles and runs under Unix.  Much faster since it doesn't reallocate
  19.  * every data structure in the inner loop(!).  Compatible with Unix diff
  20.  * output format, though it occasionally finds different sets of changed
  21.  * lines (both are valid).  -c option needs work.  Also, ftell's in
  22.  * <check> should be dumped when possible.
  23.  *
  24. From: EVERHART%ARISIA%rca.com@CSNET-RELAY.ARPA
  25. Message-Id: <8608201845.AA15181@lll-crg.ARPA>
  26. Date:     Wed, 20 Aug 86 10:34 EDT
  27. To: hoptoad!gnu@LLL-CRG.ARPA
  28. Subject:  Decus C DIFF source.
  29.  */
  30.  
  31. /*
  32.  *        D I F F
  33.  */
  34.  
  35. /* For VMS:
  36.   )BUILD  $(TKBOPTIONS) = {
  37.         TASK  = ...DIF
  38.       }
  39. */
  40.  
  41. /*
  42.  *    OSK changes: since OSK doesn't have realloc, put the size 
  43.  *    allocated in the head of each allocated region.  This code
  44.  *    assumes int is a maximally alligned type.
  45.  */
  46.  
  47. /*
  48.  * Borland Turbo C instructions.
  49.  *
  50.  * 1.  Make certain that TURBO is #defined.
  51.  * 2.  Compile in the Large model.
  52.  * 3.  Set the optimizations:
  53.  *    a) to optimize for speed, not size
  54.  *    b) to use register variables
  55.  *    c) to invoke register optimization
  56.  *    c) to invoke jump optimization
  57.  */
  58.  
  59.  
  60. #ifdef TURBO
  61. #include <alloc.h>
  62. #include <errno.h>
  63. #include <process.h>
  64. #include <stdio.h>
  65. #include <stdlib.h>
  66. #include <string.h>
  67. #else
  68. #include <stdio.h>
  69. #include <ctype.h>
  70. #endif
  71.  
  72. #ifdef unix
  73. #include <sys/types.h>
  74. #include <sys/stat.h>
  75. #endif
  76.  
  77. #ifdef vms
  78. #include      <ssdef.h>
  79. #include      <stsdef.h>
  80. #define  IO_SUCCESS  (SS | STS)
  81. #define  IO_ERROR  SS
  82. #endif
  83.  
  84. #ifdef AMIGA
  85. #ifndef MANX
  86. #ifndef LATTICE
  87. #define LATTICE 1
  88. #define ANSI 1
  89. #endif
  90. #endif
  91. #ifdef LATTICE
  92. #include <stdlib.h>
  93. #include <string.h>
  94.  
  95. extern char *_TZ;
  96. #endif
  97. #endif
  98. /*
  99.  * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  100.  */
  101. #ifndef  IO_SUCCESS
  102. #define  IO_SUCCESS  0
  103. #endif
  104. #ifndef  IO_ERROR
  105. #define  IO_ERROR  1
  106. #endif
  107.  
  108. #define  EOS      0
  109. #ifdef unix
  110. char temfile[L_tmpnam];
  111. char *tmpnam();
  112. #define  TEMPFILE  (temfile[0]? temfile: tmpnam(temfile))
  113. #else
  114. #define  TEMPFILE  "diff.tmp"
  115. #endif
  116. #define  TRUE      1
  117. #define  FALSE      0
  118.  
  119. #ifdef  pdp11
  120. #define  short  int
  121. #endif
  122.  
  123. typedef short LINENO;
  124. typedef unsigned short HASH;
  125.  
  126. typedef struct candidate {
  127.   LINENO b;        /* Line in fileB      */
  128.   LINENO a;        /* Line in fileA      */
  129.   LINENO link;    /* Previous candidate      */
  130. } CANDIDATE;
  131.  
  132. typedef struct line {
  133.   HASH   hash;    /* Hash value etc.      */
  134.   LINENO serial;  /* Line number        */
  135. } LINE;
  136.  
  137. #define MAXLINES  32760      /* depends on sizeof(short) */
  138. #define    LSIZE_INC 200      /* # of line entries to alloc at once */
  139.  
  140. LINE  *file[2];        /* Hash/line for total file  */
  141. #define  fileA  file[0]
  142. #define  fileB  file[1]
  143.  
  144. LINE  *sfile[2];        /* Hash/line after prefix  */
  145. #define  sfileA  sfile[0]
  146. #define  sfileB  sfile[1]
  147.  
  148. int  len[2];            /* Actual lines in each file  */
  149. #define  lenA  len[0]
  150. #define  lenB  len[1]
  151.  
  152. int  slen[2];        /* Squished lengths      */
  153. #define  slenA  slen[0]
  154. #define  slenB  slen[1]
  155.  
  156. int  prefix;            /* Identical lines at start  */
  157. int  suffix;            /* Identical lines at end  */
  158.  
  159. FILE  *infd[2] = { NULL, NULL };  /* Input file identifiers  */
  160. FILE  *tempfd;        /* Temp for input redirection  */
  161.  
  162. #ifndef LATTICE
  163. extern long  ftell();
  164. extern FILE *fopen();
  165. #ifdef TURBO
  166. extern void *malloc();
  167. #else
  168. extern char *malloc();
  169. #endif
  170. #endif
  171.  
  172. #ifdef ANSI
  173. int    error(char *,);
  174. char    *fgetss(char *, int, FILE *);
  175. HASH      hash(char *);
  176. HASH    newcand(LINENO, LINENO, LINENO);
  177. unsigned search(unsigned, unsigned, LINENO);
  178. unsigned subseq();
  179. #else
  180. char    *fgetss();
  181. HASH      hash();
  182. HASH    newcand();
  183. unsigned search();
  184. unsigned subseq();
  185. #endif
  186. /*
  187.  * The following vectors overlay the area defined by fileA
  188.  */
  189.  
  190. HASH     *class;      /* Unsorted line numbers  */
  191. HASH      *klist;      /* Index of element in clist  */
  192. CANDIDATE  *clist;      /* Storage pool for candidates  */
  193. int      clength = 0;      /* Number of active candidates  */
  194. #define    CSIZE_INC 50    /* How many to allocate each time we have to */
  195. int    csize = CSIZE_INC; /* Current size of storage pool */
  196.  
  197. LINENO     *match;        /* Longest subsequence  */
  198. long      *oldseek;      /* Seek position in file A  */
  199.  
  200. /*
  201.  * The following vectors overlay the area defined by fileB
  202.  */
  203.  
  204. LINENO     *member;      /* Concatenated equiv. classes  */
  205. long      *newseek;      /* Seek position in file B  */
  206. char      *textb;      /* Input from file2 for check  */
  207.  
  208. /*
  209.  * Global variables
  210.  */
  211.  
  212. int      eflag  = FALSE;  /* Edit script requested  */
  213. int      bflag  = FALSE;  /* Blank supress requested  */
  214. int      cflag  = FALSE;  /* Context printout      */
  215. int      iflag  = FALSE;  /* Ignore case requested  */
  216. char      text[257];       /* Input line from file1  */
  217. extern char  *myalloc(); /* Storage allocator      */
  218.  
  219. extern char  *compact(); /* Storage compactor      */
  220.  
  221. #ifdef  DEBUG
  222. #ifndef OSK
  223. #define  TIMING
  224. #endif
  225. #endif
  226. #ifdef  TIMING
  227. extern long  time();
  228. extern char  *358mend;
  229. long      totaltime;
  230. long      sectiontime;
  231. char      *mstart;
  232. #endif
  233.  
  234. main(argc, argv)
  235. int      argc;
  236. char      **argv;
  237. /*
  238.  * Diff main program
  239.  */
  240. {
  241.   register int  i;
  242.   register char  *ap;
  243.  
  244. #ifdef OSK
  245.   extern int _memmins;
  246.   _memmins = 16 * 1024;            /* tell OSK we will malloc a lot */
  247. #endif
  248. #ifdef  TIMING
  249.   sectiontime = time(&totaltime);
  250. #endif
  251. #ifdef vms
  252.   argc = getredirection(argc,argv);
  253. #endif
  254.   while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  255.       while (*ap != EOS) {
  256.         switch ((*ap++)) {
  257.         case 'b':
  258.               bflag++;
  259.               break;
  260.  
  261.         case 'c':
  262.           if (*ap > '0' && *ap <= '9') cflag = *ap++ - '0';
  263.           else cflag = 3;
  264.           break;
  265.  
  266.         case 'e':
  267.               eflag++;
  268.               break;
  269.  
  270.         case 'i':
  271.               iflag++;
  272.               break;
  273.  
  274.         default:
  275.               fprintf(stderr,
  276.                   "Warning, bad option '%c'\n",
  277.                   ap[-1]);
  278.               break;
  279.         }
  280.       }
  281.       argc--;
  282.       argv++;
  283.   }
  284.  
  285.   if (argc != 3)
  286.       error("Usage: diff [-options] file1 file2");
  287.   if (cflag && eflag) {
  288.       fprintf(stderr,
  289.         "Warning, -c and -e are incompatible, -c supressed.\n");
  290.       cflag = FALSE;
  291.   }
  292.   argv++;
  293.   for (i = 0; i <= 1; i++) {
  294.       if (argv[i][0] == '-' && argv[i][1] == EOS) {
  295.         infd[i] = stdin;
  296.         if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  297.             cant(TEMPFILE, "work", 1);
  298.       }
  299.       else {
  300.         infd[i] = fopen(argv[i], "r");
  301.       if (!infd[i]) cant(argv[i], "input", 2);    /* Fatal error */
  302.       }
  303.   }
  304.  
  305.   if (infd[0] == stdin && infd[1] == stdin)
  306.     error("Can't diff two things both on standard input.");
  307.  
  308.   if (infd[0] == NULL && infd[1] == NULL) {
  309.       cant(argv[0], "input", 0);
  310.       cant(argv[1], "input", 1);
  311.   }
  312. #ifdef vms
  313.   else if (infd[1] == NULL)
  314.       opendir(1, &argv[1], infd[0]);
  315.   else if (infd[0] == NULL)
  316.       opendir(0, &argv[0], infd[1]);
  317. #endif
  318.  
  319.  /*
  320.    * Read input, building hash tables.
  321.    */
  322.   input(0);
  323.   input(1);
  324.   if(lenA > MAXLINES || lenB > MAXLINES)
  325.     error("Can't handle files with more than %d lines.", MAXLINES);
  326.   squish();
  327. #ifdef  DEBUG
  328.   printf("before sort\n");
  329.   for (i = 1; i <= slenA; i++)
  330.       printf("sfileA[%d] = %6d %06o\n",
  331.         i, sfileA[i].serial, sfileA[i].hash);
  332.   for (i = 1; i <= slenB; i++)
  333.       printf("sfileB[%d] = %6d %06o\n",
  334.         i, sfileB[i].serial, sfileB[i].hash);
  335. #endif
  336.   sort(sfileA, slenA);
  337.   sort(sfileB, slenB);
  338. #ifdef  TIMING
  339.   ptime("input");
  340. #endif
  341. #ifdef  DEBUG
  342.   printf("after sort\n");
  343.   for (i = 1; i <= slenA; i++)
  344.       printf("sfileA[%d] = %6d %06o\n",
  345.         i, sfileA[i].serial, sfileB[i].hash);
  346.   for (i = 1; i <= slenB; i++)
  347.       printf("sfileB[%d] = %6d %06o\n",
  348.         i, sfileB[i].serial, sfileB[i].hash);
  349. #endif
  350.   /*
  351.    * Build equivalence classes.
  352.    */
  353.   member = (LINENO *)fileB;
  354.   equiv(); /* This will overwrite fileB */
  355.   member = (LINENO *)compact((char *)member, (slenB + 2) * sizeof (LINENO),
  356.         "squeezing member vector");
  357.     /* sfileB and fileB are no longer valid */
  358.   /*
  359.    * Reorder equivalence classes into array class[]
  360.    */
  361.   class = (HASH *)fileA;
  362.   unsort(); /* This will overwrite fileA */
  363.   class = (HASH *)compact((char *)class, (slenA + 2) * sizeof (HASH),
  364.         "compacting class vector");
  365.     /* sfileA and fileA are no longer valid */
  366. #ifdef  TIMING
  367.   ptime("equiv/unsort");
  368. #endif
  369.   /*
  370.     * Find longest subsequences
  371.    */
  372.   klist = (HASH *)myalloc((slenA + 2) * sizeof (HASH), "klist");
  373.   clist = (CANDIDATE *)myalloc(csize * sizeof (CANDIDATE), "clist");
  374.   i = subseq();
  375. #ifndef OSK
  376.   free((char *)member);
  377.   free((char *)class);
  378. #else
  379.   free((char *)member - sizeof(int));
  380.   free((char *)class - sizeof(int));
  381. #endif
  382.   match = (LINENO *)myalloc((lenA + 2) * sizeof (LINENO), "match");
  383.   unravel(klist[i]);
  384. #ifndef OSK
  385.   free((char *)clist);
  386.   free((char *)klist);
  387. #else
  388.   free((char *)clist - sizeof(int));
  389.   free((char *)klist - sizeof(int));
  390. #endif
  391. #ifdef  TIMING
  392.   ptime("subsequence/unravel");
  393. #endif
  394.   /*
  395.    * Check for fortuitous matches and output differences
  396.    */
  397.   oldseek = (long *)myalloc((lenA + 2) * sizeof (* oldseek), "oldseek");
  398.   newseek = (long *)myalloc((lenB + 2) * sizeof (* newseek), "newseek");
  399.   textb = myalloc(sizeof text, "textbuffer");
  400.   check(argv[0], argv[1]);
  401. #ifdef  TIMING
  402.   ptime("check");
  403. #endif
  404.   output(argv[0], argv[1]);
  405. #ifdef  TIMING
  406.   ptime("output");
  407.   printf("%ld seconds required\n", sectiontime - totaltime);
  408. #endif
  409.   if (tempfd != NULL) {
  410.       fclose(tempfd);
  411. #ifdef vms
  412.     remove(TEMPFILE);
  413. #else
  414.     unlink(TEMPFILE);
  415. #endif 
  416.   }
  417. }
  418.  
  419.  
  420. input(which)
  421. int      which;        /* 0 or 1 to redefine infd[]  */
  422. /*
  423.  * Read the file, building hash table
  424.  */
  425. {
  426.   register LINE      *lentry;
  427.   register int      linect = 0;
  428.   FILE        *fd;
  429.   int    lsize = LSIZE_INC;
  430.  
  431.   lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
  432.   fd = infd[which];
  433.   while (!getline(fd, text)) {
  434.     if (++linect >= lsize) {
  435.         lsize += LSIZE_INC;
  436.         lentry = (LINE *)compact((char *)lentry,
  437.           (lsize + 3) * sizeof(LINE),
  438.           "extending line vector");
  439.     }
  440.       lentry[linect].hash = hash(text);
  441.   }
  442.   /*
  443.    * If input was from stdin ("-" command), finish off the temp file.
  444.    */
  445.   if (fd == stdin) {
  446.       fclose(tempfd);
  447.       tempfd = infd[which] = fopen(TEMPFILE, "r");
  448.   }
  449.   /* If we wanted to be stingy with memory, we could realloc lentry down
  450.    * to its exact size (+3 for some odd reason) here.  No need?  */
  451.   len[which] = linect;
  452.   file[which] = lentry;
  453. }
  454.  
  455. squish()
  456. /*
  457.  * Look for initial and trailing sequences that have identical hash values.
  458.  * Don't bother building them into the candidate vector.
  459.  */
  460. {
  461.   register int  i;
  462.   register LINE  *ap;
  463.   register LINE  *bp;
  464.   int      j;
  465.   int      k;
  466.  
  467.   /*
  468.    * prefix -> first line (from start) that doesn't hash identically
  469.    */
  470.   i = 0; ap = &fileA[1]; bp = &fileB[1];
  471.   while (i < lenA && i < lenB && ap->hash == bp->hash) {
  472.       i++; ap++; bp++;
  473.   }
  474.   prefix = i;
  475.   /*
  476.    * suffix -> first line (from end) that doesn't hash identically
  477.    */
  478.   j = lenA - i;
  479.   k = lenB - i;
  480.   ap = &fileA[lenA];
  481.   bp = &fileB[lenB];
  482.   i = 0;
  483.   while (i < j && i < k && ap->hash == bp->hash) {
  484.       i++; ap--; bp--;
  485.   }
  486.   suffix = i;
  487.   /*
  488.    * Tuck the counts away
  489.    */
  490.   for (k = 0; k <= 1; k++) {
  491.       sfile[k] = file[k] + prefix;
  492.       slen[k] = len[k] - prefix - suffix;
  493.  
  494.       for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
  495.         ap->serial = i;
  496.       }
  497.   }
  498. }
  499.  
  500. sort(vector, vecsize)
  501. LINE      *vector;      /* What to sort        */
  502. int      vecsize;      /* How many to sort      */
  503. /*
  504.  * Sort hash entries
  505.  */
  506. {
  507.   register int  j;
  508.   register LINE  *aim;
  509.   register LINE  *ai;
  510.   int      mid;  
  511.   int      k;
  512.   LINE      work;
  513.  
  514.   for (j = 1; j <= vecsize; j *= 2);
  515.   mid = (j - 1);
  516.   while ((mid /= 2) != 0) {
  517.       k = vecsize - mid;
  518.       for (j = 1; j <= k; j++) {
  519.         for (ai = &vector[j]; ai > vector; ai -= mid) {
  520.             aim = &ai[mid];
  521.             if (aim->hash > ai->hash ||
  522.                   aim->hash == ai->hash &&
  523.                   aim->serial > ai->serial)
  524.               break;
  525.             work.hash = ai->hash;
  526.             ai->hash = aim->hash;
  527.             aim->hash = work.hash;
  528.             work.serial = ai->serial;
  529.             ai->serial = aim->serial;
  530.             aim->serial = work.serial;
  531.         }
  532.       }
  533.   }
  534. }
  535.  
  536. equiv()
  537. /*
  538.  * Build equivalence class vector
  539.  */
  540. {
  541.   register LINE  *ap;
  542.   register LINE     *bp;
  543.   register LINENO *mp;
  544.   register int  j;
  545.   LINE    *atop, *btop;
  546.  
  547. #ifdef  DEBUG
  548.   printf("equiv entry\n");
  549.   for (j = 1; j <= slenA; j++)
  550.       printf("sfileA[%d] = %6d %06o\n",
  551.             j, sfileA[j].serial, sfileA[j].hash);
  552.   for (j = 1; j <= slenB; j++)
  553.       printf("sfileB[%d] = %6d %06o\n",
  554.             j, sfileB[j].serial, sfileB[j].hash);
  555. #endif
  556.   j = 1;
  557.   ap = &sfileA[1];
  558.   bp = &sfileB[1];
  559.   atop = &sfileA[slenA];
  560.   while (ap <= atop && j <= slenB) {
  561.       if (ap->hash < bp->hash) {
  562.         ap->hash = 0;
  563.         ap++;
  564.       }
  565.       else if (ap->hash == bp->hash) {
  566.         ap->hash = j;
  567.         ap++;
  568.       }
  569.       else {
  570.         bp++;
  571.         j++;
  572.       }
  573.   }
  574.   while (ap <= atop) {
  575.       ap->hash = 0;
  576.       ap++;
  577.   }
  578.   sfileB[slenB + 1].hash = 0;
  579. #ifdef  DEBUG
  580.   printf("equiv exit\n");
  581.   for (j = 1; j <= slenA; j++)
  582.       printf("sfileA[%d] = %6d %06o\n",
  583.             j, sfileA[j].serial, sfileA[j].hash);
  584.   for (j = 1; j <= slenB; j++)
  585.       printf("sfileB[%d] = %6d %06o\n",
  586.             j, sfileB[j].serial, sfileB[j].hash);
  587. #endif
  588.   bp = sfileB;
  589.   btop = &sfileB[slenB];
  590.   mp = member;
  591.   while (++bp <= btop) {
  592.       *(++mp) = -(bp->serial);
  593.       while (bp[1].hash == bp->hash) {
  594.         bp++;
  595.         *(++mp) = bp->serial;
  596.       }
  597.   }
  598.   *(++mp) = -1;
  599. #ifdef  DEBUG
  600.   for (j = 0; j <= slenB; j++)
  601.       printf("member[%d] = %d\n", j, member[j]);
  602. #endif
  603. }
  604.  
  605. unsort()
  606. /*
  607.  * Build class vector
  608.  */
  609. {
  610.   HASH  *temp;
  611.   register HASH *tp;
  612.   register LINE    *ap;
  613.   register HASH *cp;
  614.   LINE *evec;
  615.   HASH *eclass;
  616. #ifdef  DEBUG
  617.   int      i;
  618. #endif
  619.  
  620.   tp = temp = (HASH *)myalloc((slenA + 1) * sizeof(HASH), "unsort scratch");
  621.   ap = &sfileA[1];
  622.   evec = &sfileA[slenA];
  623.   while (ap <= evec) {
  624. #ifdef  DEBUG
  625.       printf("temp[%2d] := %06o\n", ap->serial, ap->hash);
  626. #endif
  627.       tp[ap->serial] = ap->hash;
  628.       ap++;
  629.   }
  630.   /*
  631.    * Copy into class vector and free work space
  632.    */
  633.   cp = &class[1];
  634.   eclass = &class[slenA];
  635.   tp = &temp[1];
  636.   while (cp <= eclass)
  637.       *cp++ = *tp++;
  638. #ifndef OSK
  639.   free((char *) temp);
  640. #else
  641.   free((char *)temp - sizeof(int));
  642. #endif
  643. #ifdef  DEBUG
  644.   printf("unsort exit\n");
  645.   for (i = 1; i <= slenA; i++)
  646.       printf("class[%d] = %d %06o\n", i, class[i], class[i]);
  647. #endif
  648. }
  649.  
  650. unsigned
  651. subseq()
  652. /*
  653.  * Generate maximum common subsequence chain in clist[]
  654.  */
  655. {
  656.   int        a;
  657.   register unsigned      ktop;
  658.   register LINENO      b;
  659.   register unsigned      s;
  660.   unsigned        r;
  661.   HASH        i;
  662.   HASH           cand;
  663.  
  664.   klist[0] = newcand(0, 0, -1);
  665.   klist[1] = newcand((LINENO) (slenA + 1), (LINENO) (slenB + 1), -1);
  666.   ktop = 1;            /* -> guard entry  */
  667.   for (a = 1; a <= slenA; a++) {
  668.       /*
  669.        * For each non-zero element in fileA ...
  670.        */
  671.       if ((i = class[a]) == 0)
  672.         continue;
  673.       cand = klist[0];      /* No candidate now  */
  674.       r = 0;            /* Current r-candidate  */
  675.       do {
  676. #ifdef  DEBUG
  677.         printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
  678. #endif
  679.         /*
  680.          * Perform the merge algorithm
  681.          */
  682.         if ((b = member[i]) < 0)
  683.             b = -b;
  684. #ifdef  DEBUG
  685.         printf("search(%d, %d, %d) -> %d\n",
  686.               r, ktop, b, search(r, ktop, b));
  687. #endif
  688.         if (s = search(r, ktop, b)) {
  689.             if (clist[klist[s]].b > b) {
  690.               klist[r] = cand;
  691.               r = s;
  692.               cand = newcand((LINENO) a, b, klist[s-1]);
  693. #ifdef  DEBUG
  694.               dumpklist(ktop, "klist[s-1]->b > b");
  695. #endif
  696.             }
  697.             if (s >= ktop) {
  698.               klist[ktop + 1] = klist[ktop];
  699.               ktop++;
  700. #ifdef  DEBUG
  701.               klist[r] = cand;
  702.               dumpklist(ktop, "extend");
  703. #endif
  704.               break;
  705.             }
  706.         }
  707.       } while (member[++i] > 0);
  708.     klist[r] = cand;
  709.   }
  710. #ifdef  DEBUG
  711.   printf("last entry = %d\n", ktop - 1);
  712. #endif
  713.   return(ktop - 1);        /* Last entry found  */
  714. }
  715.  
  716. HASH
  717. newcand(a, b, pred)
  718. LINENO     a;      /* Line in fileA        */
  719. LINENO     b;      /* Line in fileB        */
  720. LINENO     pred;      /* Link to predecessor, index in cand[]  */
  721. {
  722.   register CANDIDATE  *new;
  723.  
  724.   clength++;
  725.   if (++clength >= csize) {
  726.     csize += CSIZE_INC;
  727.     clist = (CANDIDATE *)compact((char *)clist,
  728.           csize * sizeof (CANDIDATE),
  729.           "extending clist");
  730.   }
  731.   new = &clist[clength - 1];
  732.   new->a = a;
  733.   new->b = b;
  734.   new->link = pred;
  735.   return((HASH) (clength - 1));
  736. }
  737.  
  738. unsigned
  739. search(low, high, b)
  740. register unsigned  low;
  741. register unsigned  high;
  742. register LINENO       b;
  743. /*
  744.  * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
  745.  * return zero.  Else return s such that klist[s-1]->b < b and
  746.  * klist[s]->b >= b.  Note that the algorithm presupposes the two
  747.  * preset "fence" elements, (0, 0) and (slenA, slenB).
  748.  */
  749. {
  750.   register LINENO      temp;
  751.   register unsigned      mid;
  752.  
  753.   if (clist[klist[low]].b >= b)
  754.       return(0);
  755.   while ((mid = (low + high) / 2) > low) {
  756.       if ((temp = clist[klist[mid]].b) > b)
  757.         high = mid;
  758.       else if (temp < b)
  759.         low = mid;
  760.       else {
  761.         return(mid);
  762.       }
  763.   }
  764.   return(mid + 1);
  765. }
  766.  
  767.  
  768. unravel(k)
  769. register int  k;
  770. {
  771.   register int      i;
  772.   register CANDIDATE  *cp;
  773.   int        first_trailer;
  774.   int        difference;
  775.  
  776.   first_trailer = lenA - suffix;
  777.   difference = lenB - lenA;
  778. #ifdef  DEBUG
  779.   printf("first trailer = %d, difference = %d\n",
  780.       first_trailer, difference);
  781. #endif
  782.   for (i = 0; i <= lenA; i++) {
  783.       match[i] = (i <= prefix) ? i
  784.         : (i > first_trailer) ? i + difference
  785.         : 0;
  786.   }
  787. #ifdef  DEBUG
  788.   printf("unravel\n");
  789. #endif
  790.   while (k != -1) {
  791.       cp = &clist[k];
  792. #ifdef  DEBUG
  793.       if (k < 0 || k >= clength)
  794.         error("Illegal link -> %d", k);
  795.       printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
  796. #endif
  797.       match[cp->a + prefix] = cp->b + prefix;
  798.       k = cp->link;
  799.   }
  800. }
  801.  
  802.  
  803. /*
  804.  * Check for hash matches (jackpots) and collect random access indices to
  805.  * the two files.
  806.  *
  807.  * It should be possible to avoid doing most of the ftell's by noticing
  808.  * that we are not doing a context diff and noticing that if a line
  809.  * compares equal to the other file, we will not ever need to know its
  810.  * file position.  FIXME.
  811.  */
  812. check(fileAname, fileBname)
  813. char      *fileAname;
  814. char      *fileBname;
  815. {
  816.   register int  a;      /* Current line in file A  */
  817.   register int  b;      /* Current line in file B  */
  818.   int      jackpot;
  819.  
  820. /*
  821.  * The VAX C ftell() returns the address of the CURRENT record, not the
  822.  * next one (as in DECUS C or, effectively, other C's).  Hence, the values
  823.  * are "off by one" in the array.  OFFSET compensates for this.
  824.  */
  825. #ifdef vms
  826. #define OFFSET (-1)
  827. #else
  828. #define OFFSET 0
  829. #endif
  830.  
  831.   b = 1;
  832.   rewind(infd[0]);
  833.   rewind(infd[1]);
  834. /*
  835.  * See above; these would be over-written on VMS anyway.
  836.  */
  837. #ifndef vms
  838.   oldseek[0] = ftell(infd[0]);
  839.   newseek[0] = ftell(infd[1]);
  840. #endif
  841.  
  842.   jackpot = 0;
  843. #ifdef  DEBUG
  844.   printf("match vector\n");
  845.   for (a = 0; a <= lenA; a++)
  846.       printf("match[%d] = %d\n", a, match[a]);
  847. #endif
  848.   for (a = 1; a <= lenA; a++) {
  849.       if (match[a] == 0) {
  850.       /* Unique line in A */
  851.         oldseek[a+OFFSET] = ftell(infd[0]);
  852.         getline(infd[0], text);
  853.         continue;  
  854.       }
  855.       while (b < match[a]) {
  856.       /* Skip over unique lines in B */
  857.         newseek[b+OFFSET] = ftell(infd[1]);
  858.         getline(infd[1], textb);
  859.         b++;
  860.       }
  861.  
  862.     /*
  863.      * Compare the two, supposedly matching, lines.
  864.      * Unless we are going to print these lines, don't bother to
  865.      * remember where they are.  We only print matching lines
  866.      * if a context diff is happening, or if a jackpot occurs.
  867.      */
  868.     if (cflag) {
  869.         oldseek[a+OFFSET] = ftell(infd[0]);
  870.         newseek[b+OFFSET] = ftell(infd[1]);
  871.     }
  872.       getline(infd[0], text);
  873.       getline(infd[1], textb);
  874.       if (strcmp(text, textb)) {
  875. #ifdef DEBUG
  876.         fprintf(stderr,  "Spurious match:\n");
  877.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  878.             a, fileAname, text);
  879.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  880.             b, fileBname, textb);
  881. #endif
  882.         match[a] = 0;
  883.         jackpot++;
  884.       }
  885.  
  886.       b++;
  887.   }
  888.   for (; b <= lenB; b++) {
  889.       newseek[b+OFFSET] = ftell(infd[1]);
  890.       getline(infd[1], textb);
  891.   }
  892. /*
  893.  * The logical converse to the code up above, for NON-VMS systems, to
  894.  * store away an fseek() pointer at the beginning of the file.  For VMS,
  895.  * we need one at EOF...
  896.  */
  897. #ifdef vms
  898.   oldseek[lenA] = ftell(infd[0]);
  899.   getline(infd[0],text);        /* Will hit EOF...  */
  900.   newseek[lenB] = ftell(infd[1]);
  901.   getline(infd[1],textb);        /* Will hit EOF...  */
  902. #endif
  903.  
  904.   return(jackpot);
  905. }
  906.  
  907. output(fileAname, fileBname)
  908. char *fileAname, *fileBname;
  909. {
  910.   register int  astart;
  911.   register int  aend;
  912.   int      bstart;
  913.   register int    bend;
  914.  
  915.   rewind(infd[0]);
  916.   rewind(infd[1]);
  917.   match[0] = 0;
  918.   match[lenA+1] = lenB + 1;
  919.   if (!eflag) {
  920.     if (cflag) {
  921.         coutput(fileAname, fileBname);
  922.         return;
  923.     } else {
  924.         /*
  925.          * Normal printout
  926.          */
  927.         for (astart = 1; astart <= lenA; astart = aend + 1) {
  928.         /*
  929.          * New subsequence, skip over matching stuff
  930.          */
  931.         while (astart <= lenA &&
  932.                match[astart] == (match[astart - 1] + 1))
  933.             astart++;
  934.         /*
  935.          * Found a difference, setup range and print it
  936.          */
  937.         bstart = match[astart - 1] + 1;
  938.         aend = astart - 1;
  939.         while (aend < lenA && match[aend + 1] == 0)
  940.             aend++;
  941.         bend = match[aend + 1] - 1;
  942.         match[aend] = bend;
  943.         change(astart, aend, bstart, bend);
  944.         }
  945.     }
  946.   }
  947.   else {
  948.       /*
  949.        * Edit script output -- differences are output "backwards"
  950.        * for the benefit of a line-oriented editor.
  951.        */
  952.       for (aend = lenA; aend >= 1; aend = astart - 1) {
  953.         while (aend >= 1
  954.               && match[aend] == (match[aend + 1] - 1)
  955.               && match[aend] != 0)
  956.             aend--;
  957.         bend = match[aend + 1] - 1;
  958.         astart = aend + 1;
  959.         while (astart > 1 && match[astart - 1] == 0)
  960.             astart--;
  961.         bstart = match[astart - 1] + 1;
  962.         match[astart] = bstart;
  963.         change(astart, aend, bstart, bend);
  964.       }
  965.   }
  966.   if (lenA == 0)
  967.       change(1, 0, 1, lenB);
  968. }
  969.  
  970.  
  971. coutput(fileAname, fileBname)
  972. char *fileAname, *fileBname;
  973. {
  974.   int    astart;
  975.   int    aend;
  976.   int    bstart;
  977.   int    bend = 0;
  978.   int    change, ctmp, cFirst, cOld;
  979.   int    a1start, a1end, b1start, b1end, a2start, a2end, b2start, b2end;
  980.   int    astartLast, aendLast, bstartLast, bendLast;
  981.   int    low;
  982.   int    numDifferences = 0;
  983.  
  984. #define CINSERTION    1
  985. #define CDELETION    2
  986. #define CCHANGE        4
  987.   for (astart = 1; astart <= lenA; astart = aend + 1) {
  988.     if(!(change = findentry(&astart, &aend, &bstart, &bend)))
  989.         break;
  990.     /* find last entry to print in this diff */
  991.     cFirst = change;
  992.     astartLast = astart;
  993.     aendLast = a1end = aend;
  994.     bstartLast = bstart;
  995.     bendLast = b1end = bend;
  996.     for(a1start = aendLast + 1; a1start <= lenA; a1start = a1end + 1) {
  997.         if(!(ctmp = findentry(&a1start, &a1end, &b1start, &b1end)) ||
  998.            ((a1start - aendLast) >= 2*cflag &&
  999.         (b1start - bendLast) >= 2*cflag))
  1000.         break;
  1001.         change |= ctmp;
  1002.         astartLast = a1start;
  1003.         aendLast = a1end;
  1004.         bstartLast = b1start;
  1005.         bendLast = b1end;
  1006.     }
  1007.     if(!numDifferences++)
  1008.         printHeader(fileAname, fileBname);
  1009.     fputs("***************\n*** ", stdout);
  1010.     range(astart, aendLast, 0);
  1011.     fputs(" ****\n", stdout);
  1012.     if (change & (CDELETION | CCHANGE)) {
  1013.         a1start = astart; a1end = aend; b2end = bend;
  1014.         cOld = cFirst;
  1015.         low = astart - cflag;
  1016.         while (a1start < astartLast) {
  1017.         a2start = a1end + 1;
  1018.         ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
  1019.         fetch(oldseek, a1start, a1end, low, a2start - 1, lenA,
  1020.               infd[0], (cOld & CDELETION) ? "- " : "! ");
  1021.         cOld = ctmp;
  1022.         low = a2start;
  1023.         a1start = a2start;
  1024.         a1end = a2end;
  1025.         }
  1026.         fetch(oldseek, astartLast, aendLast, low, aendLast + cflag, lenA,
  1027.           infd[0], (cOld & CDELETION) ? "- " : "! ");
  1028.     }
  1029.     fputs("--- ", stdout);
  1030.     range(bstart, bendLast, 1);
  1031.     fputs(" ----\n", stdout);
  1032.     if (change & (CINSERTION | CCHANGE)) {
  1033.         a2start = astart; a2end = aend;
  1034.         b1start = bstart; b1end = b2end = bend;
  1035.         cOld = cFirst;
  1036.         low = bstart - cflag;
  1037.         while (a2start < astartLast) {
  1038.         a2start = a2end + 1;
  1039.         ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
  1040.         fetch(newseek, b1start, b1end, low, b2start - 1, lenB,
  1041.               infd[1], (cOld & CINSERTION) ? "+ " : "! ");
  1042.         cOld = ctmp;
  1043.         low = b2start;
  1044.         b1start = b2start;
  1045.         b1end = b2end;
  1046.         }
  1047.         fetch(newseek, bstartLast, bendLast, low, bendLast + cflag, lenB,
  1048.           infd[1], (cOld & CINSERTION) ? "+ " : "! ");
  1049.     }
  1050.     aend = aendLast;
  1051.     bend = bendLast;
  1052.   }
  1053.   if (lenA == 0 && lenB > 0) {
  1054.     numDifferences++;
  1055.     printHeader(fileAname, fileBname);
  1056.     cchange(1, 0, 1, lenB);
  1057.   }
  1058.   if (!numDifferences)
  1059.     printf("No differences encountered\n");
  1060. }
  1061.  
  1062.  
  1063. printHeader(fileAname, fileBname)
  1064. char *fileAname, *fileBname;
  1065. {
  1066.   long  fileDate;
  1067. #ifdef unix
  1068.   struct stat statbuf;
  1069. #endif
  1070.  
  1071. #ifdef AMIGA
  1072. #ifdef LATTICE
  1073.   _TZ = "GMT0";
  1074. #endif
  1075.   if(infd[0] == tempfd)
  1076.     fileDate = time(0);
  1077.   else
  1078.     fileDate = getft(fileAname);
  1079.   printf("*** %s\t%s", fileAname, ctime(&fileDate));
  1080.   if(infd[1] == tempfd)
  1081.     fileDate = time(0);
  1082.   else
  1083.     fileDate = getft(fileBname);
  1084.   printf("--- %s\t%s", fileBname, ctime(&fileDate));
  1085. #else
  1086. #ifdef unix
  1087.   if(infd[0] == tempfd)
  1088.     fileDate = time(0);
  1089.   else {
  1090.     fstat(fileno(infd[0]), &statbuf);
  1091.     fileDate = statbuf.st_mtime;
  1092.   }
  1093.   printf("*** %s\t%s", fileAname, ctime(&fileDate));
  1094.   if(infd[1] == tempfd)
  1095.     fileDate = time(0);
  1096.   else {
  1097.     fstat(fileno(infd[1]), &statbuf);
  1098.     fileDate = statbuf.st_mtime;
  1099.   }
  1100.   printf("--- %s\t%s", fileBname, ctime(&fileDate));
  1101. #else
  1102.   printf("*** %s\n--- %s\n", fileAname, fileBname);
  1103. #endif
  1104. #endif
  1105. }
  1106.  
  1107.  
  1108. int
  1109. findentry(astartp, aendp, bstartp, bendp)
  1110. int *astartp, *aendp, *bstartp, *bendp;
  1111. {
  1112.   int save;
  1113.   register int astart = *astartp;
  1114.   register int aend;
  1115.  
  1116.   if(astart > lenA)
  1117.     return(0);
  1118.   save = match[astart - 1];
  1119.   match[astart - 1] = *bendp;
  1120.   /* Skip over matching stuff */
  1121.   while (astart <= lenA && match[astart] == (match[astart - 1] + 1))
  1122.     astart++;
  1123.   *bstartp = match[astart - 1] + 1;
  1124.   aend = astart - 1;
  1125.   while (aend < lenA && match[aend + 1] == 0)
  1126.     aend++;
  1127.   *bendp = match[aend + 1] - 1;
  1128.   match[*astartp - 1] = save;
  1129.   *astartp = astart;
  1130.   *aendp = aend;
  1131.   if (astart > aend) {
  1132.       if (*bstartp > *bendp)
  1133.         return(0);
  1134.     else
  1135.         return(CINSERTION);
  1136.   } else if (*bstartp > *bendp)
  1137.     return(CDELETION);
  1138.   else
  1139.     return(CCHANGE);
  1140. }
  1141.  
  1142.  
  1143. /*
  1144.  * Output a non context diff change entry:
  1145.  *   fileA[astart..aend] changed to fileB[bstart..bend]
  1146.  */
  1147. change(astart, aend, bstart, bend)
  1148. int      astart;
  1149. int      aend;
  1150. int      bstart;
  1151. int      bend;
  1152. {
  1153.   char c;
  1154.   /*
  1155.    * This catches a "dummy" last entry
  1156.    */
  1157.   if (astart > aend && bstart > bend)
  1158.       return;
  1159.   c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  1160.   if (c == 'a')
  1161.     range(astart-1, astart-1, 0);    /* Addition: just print one odd # */
  1162.   else
  1163.     range(astart, aend, 0);        /* Print both, if different */
  1164.   putchar(c);
  1165.   if (!eflag) {
  1166.     if (c == 'd')
  1167.         range(bstart-1, bstart-1, 1); /* Deletion: just print one odd # */
  1168.     else
  1169.         range(bstart, bend, 1);    /* Print both, if different */
  1170.   }
  1171.   putchar('\n');
  1172.   if (c != 'a') {
  1173.       fetch(oldseek, astart, aend, 0, 0, lenA, infd[0], "< ");
  1174.     if (astart <= aend && bstart <= bend)
  1175.         printf("---\n");
  1176.   }
  1177.   if (c != 'd')
  1178.        fetch(newseek, bstart, bend, 0, 0, lenB, infd[1], eflag ? "" : "> ");
  1179.   if (eflag && bstart <= bend)
  1180.       printf(".\n");
  1181. }
  1182.  
  1183.  
  1184. /*
  1185.  * Output a context diff change entry:
  1186.  *   fileA[astart..aend] changed to fileB[bstart..bend]
  1187.  */
  1188. cchange(astart, aend, bstart, bend)
  1189. int      astart;
  1190. int      aend;
  1191. int      bstart;
  1192. int      bend;
  1193. {
  1194.   char c;
  1195.  
  1196.   /*
  1197.    * This catches a "dummy" last entry
  1198.    */
  1199.   if (astart > aend && bstart > bend)
  1200.       return;
  1201.   c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  1202.   fputs("***************\n*** ", stdout);
  1203.   range(astart, aend, 0);
  1204.   fputs(" ****\n", stdout);
  1205.   fetch(oldseek, astart, aend, astart - cflag, aend + cflag, lenA, infd[0],
  1206.     c=='d' ? "- " : "! ");
  1207.   fputs("--- ", stdout);
  1208.   range(bstart, bend, 1);
  1209.   fputs(" ----\n", stdout);
  1210.   fetch(newseek, bstart, bend, bstart - cflag, bend + cflag, lenB, infd[1],
  1211.     c=='a' ? "+ " : "! ");
  1212. }
  1213.  
  1214. range(from, to, w)
  1215. int      from;
  1216. int      to;
  1217. int    w;
  1218. /*
  1219.  * Print a range
  1220.  */
  1221. {
  1222.   if (cflag) {
  1223.     if((from -= cflag) <= 0) from = 1;
  1224.     if((to += cflag) > len[w]) to = len[w];
  1225.     if(!to) from = 0;
  1226.   }
  1227.   if (to > from) {
  1228.     printf("%d,%d", from, to);
  1229.   } else if (to < from) {
  1230.     printf("%d,%d", to, from);
  1231.   } else {
  1232.     printf("%d", from);
  1233.   }
  1234. }
  1235.  
  1236.  
  1237. fetch(seekvec, start, end, low, high, trueend, fd, pfx)
  1238. long      *seekvec;
  1239. register int  start;
  1240. register int  end;
  1241. int    low;
  1242. int    high;
  1243. int      trueend;
  1244. FILE      *fd;
  1245. char      *pfx;
  1246. /*
  1247.  * Print the appropriate text
  1248.  */
  1249. {
  1250.   register int  i;
  1251.   register int    first;
  1252.   register int    last;
  1253.  
  1254.   if (cflag) {
  1255.     if((first = low) <= 0) first = 1;
  1256.     if((last = high) > trueend) last = trueend;
  1257.   } else {
  1258.     first = start;
  1259.     last = end;
  1260.   }
  1261.   if (first > last)
  1262.       return;
  1263.   if (fseek(fd, seekvec[first], 0) != 0) {
  1264.       printf("?Can't read line %d at %08lx (hex) in file%c\n",
  1265.         start, seekvec[first],
  1266.         (fd == infd[0]) ? 'A' : 'B');
  1267.   }
  1268.   else {
  1269.       for (i = first; i <= last; i++) {
  1270.         if (fgetss(text, sizeof text, fd) == NULL) {
  1271.              printf("** Unexpected end of file\n");
  1272.             break;
  1273.         }
  1274. #ifdef DEBUG
  1275.         printf("%5d: %s%s\n", i, pfx, text);
  1276. #else
  1277.         fputs((cflag && (i<start || i>end)) ? "  " : pfx, stdout);
  1278.         fputs(text, stdout);
  1279.       putchar('\n');
  1280. #endif
  1281.       }
  1282.   }  
  1283. }
  1284.  
  1285. /*
  1286.  * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
  1287.  * The terminating newline is always removed.  If "-b" was given, trailing
  1288.  * whitespace (blanks and tabs) are removed and strings of blanks and
  1289.  * tabs are replaced by a single blank.  Getline() does all hacking for
  1290.  * redirected input files.
  1291.  */
  1292. int
  1293. getline(fd, buffer)
  1294. FILE      *fd;
  1295. char      *buffer;
  1296. {
  1297.   register char  *top;
  1298.   register char  *fromp;
  1299.   register char  c;
  1300.  
  1301.   if (fgetss(buffer, sizeof text, fd) == NULL) {
  1302.       *buffer = EOS;
  1303.       return(TRUE);
  1304.   }
  1305.   if (fd == stdin) {
  1306.       fputs(buffer, tempfd);
  1307.     putc('\n', tempfd);
  1308.   }
  1309.   if (bflag || iflag) {
  1310.       top = buffer;
  1311.       fromp = buffer;
  1312.       while ((c = *fromp++) != EOS) {
  1313.         if (bflag && (c == ' ' || c == '\t')) {
  1314.             c = ' ';
  1315.             while (*fromp == ' ' || *fromp == '\t')
  1316.               fromp++;
  1317.         }
  1318.         if (iflag)
  1319.             c = tolower(c);
  1320.         *top++ = c;
  1321.       }
  1322.       if (bflag && top[-1] == ' ')
  1323.         top--;
  1324.       *top = EOS;
  1325.   }
  1326.   return(FALSE);
  1327. }
  1328. static unsigned short crc16a[] = {
  1329.   0000000,  0140301,  0140601,  0000500,
  1330.   0141401,  0001700,  0001200,  0141101,
  1331.   0143001,  0003300,  0003600,  0143501,
  1332.   0002400,  0142701,  0142201,  0002100,  
  1333. };
  1334. static unsigned short crc16b[] = {
  1335.   0000000,  0146001,  0154001,  0012000,
  1336.   0170001,  0036000,  0024000,  0162001,
  1337.   0120001,  0066000,  0074000,  0132001,
  1338.   0050000,  0116001,  0104001,  0043000,
  1339. };
  1340.  
  1341. unsigned short
  1342. hash(buffer)
  1343. char      *buffer;
  1344. /*
  1345.  * Return the CRC16 hash code for the buffer
  1346.  * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
  1347.  */
  1348. {
  1349.   register unsigned short  crc;
  1350.   register char      *tp;
  1351.   register short       temp;
  1352.  
  1353.   crc = 0;
  1354.   for (tp = buffer; *tp != EOS;) {
  1355.       temp = *tp++ ^ crc;  /* XOR crc with new char  */
  1356.       crc = (crc >> 8)
  1357.         ^ crc16a[(temp & 0017)]
  1358.         ^ crc16b[(temp & 0360) >> 4];
  1359.   }
  1360. #ifdef  DEBUG_ALL
  1361.   printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
  1362. #endif
  1363.   return((crc == 0) ? (unsigned short) 1 : crc);
  1364. }      
  1365.  
  1366.  
  1367. #ifdef vms
  1368. opendir(which, arg, okfd)
  1369. int      which;      /* Which file to open (0 or 1)      */
  1370. char      **arg;      /* File name argument, &argv[which]  */
  1371. FILE      *okfd;      /* File name (already open)      */
  1372. {
  1373.   register char      *tp;
  1374.   register int      c;
  1375.   register char      *newname;
  1376.  
  1377.   fgetname(okfd, text);
  1378.   /*
  1379.    * Skip over device name
  1380.    */
  1381.   for (tp = text; (c = *tp) && c != ':'; tp++);
  1382.   if (c)  tp++;
  1383.   else  tp = text;
  1384.   /*
  1385.    * Skip over [UIC] or [PPN] if present
  1386.    */
  1387.   if (*tp == '[' || *tp == '(') {
  1388.       while ((c = *tp++) && c != ']' && c != ')');
  1389.       if (c == 0) {
  1390.         fprintf(stderr, "?Bug: bad file name \"%s\"\n",
  1391.               text);
  1392.         tp--;
  1393.       }
  1394.   }
  1395.   strcpy(text, tp);
  1396.   /*
  1397.    * Don't include version
  1398.    */
  1399.   for (tp = text; (c = *tp) && c != ';'; tp++);
  1400.   *tp = 0;
  1401.   /*
  1402.    * Now, text has the file name, tp - text, its length,
  1403.    * and *arg the (possible) directory name.  Create a new
  1404.    * file name for opening.
  1405.    */
  1406. #ifndef    OSK
  1407.   if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
  1408.       error("Out of space at start");
  1409. #else
  1410.   newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
  1411. #endif
  1412.   concat(newname, *arg, text, NULL);
  1413.   if ((infd[which] = fopen(newname, "r")) == NULL)
  1414.       cant(*arg, "constructed input", 1);
  1415.   else
  1416.       *arg = newname;
  1417. }
  1418. #endif
  1419.  
  1420. char *
  1421. myalloc(amount, why)
  1422. int      amount;
  1423. char      *why;
  1424. /*
  1425.  * Allocate or crash.
  1426.  */
  1427. {
  1428.   register char  *pointer;
  1429.  
  1430. #ifdef OSK
  1431.   amount += sizeof(int);
  1432. #endif
  1433.   if ((pointer = malloc((unsigned) amount)) == NULL)
  1434.       noroom(why);
  1435. #ifdef OSK
  1436.   *((int *)pointer) = amount;
  1437.   pointer += sizeof(int);
  1438. #ifdef DEBUG
  1439.   fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
  1440. #endif
  1441. #endif
  1442.  
  1443.   return (pointer);
  1444. }
  1445.  
  1446.  
  1447. /*
  1448.  * Reallocate pointer, compacting storage
  1449.  *
  1450.  * The "compacting storage" part is probably not relevant any more.
  1451.  * There used to be horrid code here that malloc'd one byte and freed
  1452.  * it at magic times, to cause garbage collection of the freespace
  1453.  * or something.  It's safely gone now, you didn't have to see it.
  1454.  *    -- John Gilmore, Nebula Consultants, Sept 26, 1986
  1455.  */
  1456. char *
  1457. compact(pointer, new_amount, why)
  1458. char      *pointer;
  1459. int      new_amount;
  1460. char      *why;
  1461. {
  1462.   register char *new_pointer;
  1463.  
  1464. #ifndef OSK
  1465. #ifdef TURBO
  1466.   extern void *realloc();
  1467. #else
  1468.   extern char *realloc();
  1469. #endif
  1470.  
  1471.   if ((new_pointer =  realloc(pointer, (unsigned) new_amount)) == NULL){
  1472.       noroom(why);
  1473.   }
  1474. #else
  1475.   register int old_amount;
  1476.   new_amount += sizeof(int);
  1477.   if((new_pointer = malloc(new_amount)) == NULL) noroom(why);
  1478.   *(int *)new_pointer = new_amount;
  1479.   new_pointer += sizeof(int);
  1480.   old_amount = *(((int *)pointer)-1);
  1481.   /* _strass is like bcopy with the first two arguments reversted */
  1482.   _strass(new_pointer, pointer, (new_amount <= old_amount ?
  1483.       new_amount : old_amount) - sizeof(int));
  1484. #ifdef DEBUG
  1485.   fprintf(stderr, "compact %d to %d from %06o to %06o\n", 
  1486.     old_amount, new_amount, pointer, new_pointer);
  1487. #endif
  1488.   free(pointer - sizeof(int));
  1489. #endif
  1490.  
  1491. #ifndef OSK
  1492. #ifdef  DEBUG
  1493.   if (new_pointer != pointer) {
  1494.       fprintf(stderr, "moved from %06o to %06o\n",
  1495.         pointer, new_pointer);
  1496.   }
  1497. /*  rdump(new_pointer, why);
  1498. */
  1499. #endif
  1500. #endif
  1501.   return (new_pointer);
  1502. }
  1503.  
  1504. noroom(why)
  1505. char      *why;
  1506. {
  1507.   fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
  1508.   exit(IO_ERROR);
  1509. }
  1510.  
  1511. #ifdef  DEBUG
  1512. rdump(pointer, why)
  1513. int      *pointer;
  1514. char      *why;
  1515. /*
  1516.  * Dump memory block
  1517.  */
  1518. {
  1519.   int  *last;
  1520.   int  count;
  1521.  
  1522.   last = ((int **)pointer)[-1];
  1523.   fprintf(stderr, "dump %s of %06o -> %06o, %d words",
  1524.         why, pointer, last, last - pointer);
  1525.   last = (int *)(((int) last) & ~1);
  1526.   for (count = 0; pointer < last; ++count) {
  1527.       if ((count & 07) == 0) {
  1528.         fprintf(stderr, "\n%06o", pointer);
  1529.       }
  1530.       fprintf(stderr, "\t%06o", *pointer);
  1531.       pointer++;
  1532.   }
  1533.   fprintf(stderr, "\n");
  1534. }
  1535. #endif
  1536. cant(filename, what, fatalflag)
  1537. char      *filename;
  1538. char      *what;
  1539. int      fatalflag;
  1540. /*
  1541.  * Can't open file message
  1542.  */
  1543. {
  1544.   fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
  1545. #ifndef    OSK
  1546.   perror((char *)NULL);
  1547. #else
  1548.   prerr(0, errno);
  1549. #endif
  1550.   if (fatalflag) {
  1551.       exit(fatalflag);
  1552.   }
  1553. }
  1554. #ifdef  DEBUG
  1555. dump(d_linep, d_len, d_which)
  1556. LINE  *d_linep;
  1557. {
  1558.   register int i;
  1559.   
  1560.   printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
  1561.   printf("linep @ %06o\n", d_linep);
  1562.   for (i = 0; i <= d_len; i++) {
  1563.       printf("%3d  %6d  %06o\n", i,
  1564.             d_linep[i].serial, d_linep[i].hash);
  1565.   }
  1566. }
  1567.  
  1568. dumpklist(kmax, why)
  1569. int  kmax;
  1570. char  *why;
  1571. /*
  1572.  * Dump klist
  1573.  */
  1574. {
  1575.   register int      i;
  1576.   register CANDIDATE  *cp;
  1577.   register int      count;
  1578.  
  1579.   printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
  1580.   for (i = 0; i <= kmax; i++) {
  1581.       cp = &clist[klist[i]];
  1582.       printf("%2d %2d", i, klist[i]);
  1583.       if (cp >= &clist[0] && cp < &clist[clength])
  1584.         printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
  1585.       else if (klist[i] == -1)
  1586.         printf(" End of chain\n");
  1587.       else  printf(" illegal klist element\n");
  1588.   }
  1589.   for (i = 0; i <= kmax; i++) {
  1590.       count = -1;
  1591.       for (cp = (CANDIDATE *)klist[i]; cp > &clist[0]; 
  1592.         cp = (CANDIDATE *)&cp->link) {
  1593.         if (++count >= 6) {
  1594.             printf("\n    ");
  1595.             count = 0;
  1596.         }
  1597.         printf(" (%2d: %2d,%2d -> %d)",
  1598.             cp-clist, cp->a, cp->b, cp->link);
  1599.       }
  1600.       printf("\n");
  1601.   }
  1602.   printf("*\n");
  1603. }
  1604. #endif
  1605. #ifdef  TIMING
  1606. ptime(why)
  1607. char      *why;
  1608. /*
  1609.  * Dump time buffer
  1610.  */
  1611. {
  1612.   long  ttemp;
  1613.  
  1614.   ttemp = time(NULL);
  1615.   printf("%ld seconds for %s\n",
  1616.       ttemp - sectiontime, why);
  1617.   sectiontime = ttemp;
  1618. }
  1619. #endif
  1620.  
  1621. /*
  1622.  *        s t r e q . c
  1623.  */
  1624.  
  1625. /*)LIBRARY
  1626. */
  1627.  
  1628. #ifdef  DOCUMENTATION
  1629.  
  1630. title  streq  String Equality Test
  1631. index      String equality test
  1632.  
  1633. synopsis
  1634.   .s.nf
  1635.   streq(a, b);
  1636.   char      *a;
  1637.   char      *b;
  1638.   .s.f
  1639. Description
  1640.  
  1641.   Return TRUE if the strings are equal.
  1642.  
  1643. Bugs
  1644.  
  1645. #endif
  1646.  
  1647. /* #define  EOS  0
  1648. #define  FALSE  0
  1649. #define  TRUE  1
  1650. */
  1651. int
  1652. streq(s1, s2)
  1653. register char  *s1;
  1654. register char  *s2;
  1655. /*
  1656.  * TRUE if strings are identical
  1657.  */
  1658. {
  1659.   while (*s1++ == *s2) {
  1660.       if (*s2++ == EOS)
  1661.       return (TRUE);
  1662.   }
  1663.   return (FALSE);
  1664. }
  1665. /*
  1666.  *        e r r o r . c
  1667.  */
  1668.  
  1669. /*)LIBRARY
  1670. */
  1671.  
  1672. #ifdef  DOCUMENTATION
  1673.  
  1674. title  error  Fatal Error Exit
  1675. index      Fatal error exit
  1676.  
  1677. synopsis
  1678.   .s.nf
  1679.   _error()
  1680.  
  1681.   error(format, args)
  1682.   char      *format;
  1683.   .s.f
  1684. documentation
  1685.  
  1686.   Fatal error exits.  _error() halts, error() prints something
  1687.   on stderr and then halts.
  1688.  
  1689. bugs
  1690.  
  1691.   Not a real vararg function. Only handles up to a fixed number of args.
  1692.  
  1693. #endif
  1694.  
  1695. /* VARARGS */
  1696. error(format, arg1, arg2)
  1697. char      *format;
  1698. int arg1, arg2;
  1699. /*
  1700.  * Error message before retiring.
  1701.  */
  1702. {
  1703.   fprintf(stderr, format, arg1, arg2);
  1704.   putc('\n', stderr);
  1705.   _error();
  1706. }
  1707.  
  1708. _error()
  1709. {
  1710.   exit(1);
  1711. }
  1712.  
  1713. /*
  1714.  * Fgetss() is like fgets() except that the terminating newline
  1715.  * is removed.
  1716.  */
  1717. char *fgetss(s, n, iop)
  1718. char *s;
  1719. FILE *iop;
  1720. {
  1721.   int len;
  1722.  
  1723.   s[n - 1] = 0;
  1724.   if(fgets(s, n-1, iop) == NULL)
  1725.     return(NULL);
  1726.   len = strlen(s);
  1727.   if(s[len - 1] == '\n')
  1728.     s[len - 1] = 0;
  1729.   return(s);
  1730. }
  1731.